Routing is the technique by which a transaction data packet finds its way form one host computer/server to another in the Internet. A data packet may mean any packet, text message, video, voice, or the like. In the Internet there are three major aspects of routing: a physical address determination, a selection of inter-network routers and gateways, and symbolic and numeric addresses.
The first of these is important when an IP data packet is to be transmitted from a computer. The IP data packet is typically encapsulated within whatever frame format is in use on the local network or networks to which the computer is attached. This encapsulation clearly requires the inclusion of a local network address or physical address within the frame.
The second of these is necessary because the Internet consists of a number of local networks interconnected by one or more gateways. Such gateways, generally known as routers, sometimes have physical connections or ports onto many networks. The determination of the appropriate gateway and port for a particular IP packet is called routing and also involves gateways interchanging information in standard ways.
The third aspect, which involves address translation from a reasonably human friendly form to numeric IP addresses, is performed by a system known as the Domain Name System (DNS). If a computer/server is to transmit an IP packet, it encapsulates the packet in a frame appropriate to the physical medium of the network it is attached to. For the successful transmission of such a frame it is necessary to determine the physical address of the destination computer. This can be achieved fairly simply using a table that will map IP addresses to physical addresses, such a table may include addresses for IP nets and a default address as well as the physical addresses corresponding to the IP addresses of locally connected computers. Such a table could be configured into a file and read into memory at boot up time. However it is normal practice for a computer to use a protocol known as ARP (Address Resolution Protocol) and defined by the standard Request For Comments 826 (RFC 826) which established the conversion of network protocol addresses to 48-bit Ethernet addresses for transmission on Ethernet hardware (also known as STD0037). This is operated dynamically to maintain the translation table known as the ARP cache, which is useful to the routing process.
One of the main reasons for the prevalence of the Internet relates to its routing mechanism. Routing of the Internet has two key features: flexibility and scalability. The Internet provides dynamic routing based on the exchange of the routing information among routers. Routers, or gateways are computers/servers that contain some knowledge about the topology of the network and have the ability to “route” data packets between the networks they are aware of. For example, when a network route becomes unavailable because of some troubles, an alternative route will be prepared automatically. Also, the packet processing at the routers is simple (e.g., FIFO) to reduce the overhead of packet forwarding at the router. So from a users' point of view, any packet transmission delay is an important metric since it directly affects the end-to-end performance.
A Quality Of Service (QOS) approach gives an Internet Service Provider (ISP) control of how pipe's bandwidths are shared among different users. The ISP communicates its sharing policy to the users, and how delivery service typically depends also on other ISP's traffic, and on the destination path of a data packet. One QOS objective is to deliver high priority data packets either before or more efficiently than normal and low priority data packets. To achieve this goal, packet traffic shaping techniques and prioritization methods have been developed. Previous methods have partitioned access to the Internet network into logical pipes and a user incurs a cost for use of each of the logical pipes. However, current switching technologies used for the Internet do not provide a guaranteed quality of service. In addition, there is no apparent direct relationship between the cost for the connection and the quality of service, except for obvious level differences between a direct digital connection (e.g., ISDN) and an analog (modem) connection. Typical ISPs charges for Internet access tend to depend on a user's personal preference, that is either a fixed rate pricing with unlimited access or a rate pricing based only on connection time, i.e. usage-sensitive pricing. Unlike the fixed rate user preference, the case of usage-sensitive pricing for the cost for each transmitted packet typically limits over-usage of the pipes bandwidths, which may facilitate an improved Internet traffic via self-regulation. There are many known proposals for various examples of usage-sensitive pricing for the Internet.
In one example, the pipes differ primarily with respect to their usage-sensitive pricing to the users. Each user will select a pipe or pipes that offers the desired QOS level. Therefore, traffic can be accordingly heavy on the lowest priced pipes than on the highest priced pipes. A user might switch to higher priority pipes whenever a higher QOS level is desired, and vice-versa for a lower QOS level.
To accommodate packet routing via all the allocated logical pipes, a round robin (RR) queuing method has been widely utilized in the industry. In round robin queuing, a number of pipes are established for temporarily holding data packets while the data packets await delivery. These logical pipes are distributed in an appropriate hierarchy from the highest priority pipe to the lowest priority pipe. A data packet can be assigned to one of the logical pipes based on a predetermined QOS level chosen by the user. The round robin method involves rotating the delivery of an identical number of data packets from the allocated pipes, starting with the pipe with the highest priority level to the pipe with the lowest priority level then circling back to the initial pipe. Therefore, all the allocated pipes are utilized equally regardless of their respective QOS level.
Another round robin method is a weighted round robin (WRR) queuing. Weighted round robin queuing utilizes the higher priority pipes more frequently than the lower priority pipes. That is a greater number of data packets are sent from the higher priority pipes than from the lower priority pipes for each rotation through the allocated logical pipes.
However these methods do not utilize any recent traffic condition on the allocated pipes as a transaction criterion. This traffic condition aspect is generally treated by a network congestion control function and more particularly by a traffic policing process, which is typically performed at the network control points, such as routers and bridges. In order to track packet transmission performance, one method utilizes a Round Trip Time (RTT) evaluation for the transmitted data packets. An RTT represents a time interval between the sending of a packet and the receipt of its delivery acknowledgement, and is a key function in many reliable transport protocols.
Furthermore, to keep a preferable packet transmission performance on the allocated logical pipes, an accurate running estimate of RTT's corresponding to recently transmitted packets can be useful. Indeed, a process that might help predict future RTTs on these logical pipes might help ISP's meet the users desired QOS levels by rearranging or redistributing, for an appropriate period of time, the usage of the allocated logical pipes.
Hence, a transaction routing method that utilizes appropriate priority among pipes as well as recent traffic network conditions would be desirable to ensure that each user gets the quality of service (QOS) it has been guaranteed on the Internet. Accordingly, there is a need for a transaction routing method that optimizes the transmission of data packets on the Internet, and is concerned with effectively providing a user desirable QOS level.